package Algorithm;
/********************************/
/*数组相关的题型*/

import java.util.Arrays;
import java.util.HashMap;

/********************************/
public class Work {
    /*这个类用来写一些,关于算法入门的题*/

    /*1. 核心考点：数组相关，特性观察，时间复杂度把握 （day1）
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递
增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数*/
    /*/数组操作问题
//解决思路：
//如数组样式如下：
// 1 2 3 4
// 2 3 4 5
// 3 4 5 6
//正常查找的过程，本质就是排除的过程，如果双循环查找，本质是一次排除一个，效率过低
//根据题面要求，我们可以采取从右上角（或左下角）进行比较（想想为什么？），这样可以做到一次排除一行或者一列*/
    //语言切换时，OJ有时候会让同学们改类名，不要改，要不然会出现奇怪错误，应该是网站的bug

    public boolean Find(int target, int [][] array) {
        if(array == null){
            return false;
        }
        int i = 0;
        int j = array[0].length - 1;
        while( i < array.length && j >= 0){
            if(target < array[i][j]){//array[i][j]一定是当前行最大的，当前列最小的
                //target < array[i][j] 排除当前列
                j--;
            }
            else if(target > array[i][j]){
                //target > array[i][j] 排除当前行
                i++;
            } else{
                //找到
                return true;
            }
        }
        return false;
    }


        /*把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋
    转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的
    所有元素都大于0，若数组大小为0，请返回0
    */
        //数组问题，本质其实是一个求最小值问题
    //方法一：理论上，遍历一次即可，但是我们可以根据题面使用稍微高效且更简单一点的做法
    //按照要求，要么是一个非递减排序的数组（最小值在最开始），要么是一个旋转(最小值在中间某个地方)
    //而且，旋转之后有个特征，就是在遍历的时候，原始数组是非递减的，旋转之后，就有可能出现递减，引起递减的数字，就是最小值
    //方法二：采用二分查找的方式，进行定位
    //定义首尾下标，因为是非递减数组旋转，所以旋转最后可以看做成两部分，前半部分整体非递减，后半部分整体非递减，前半部分整体大于后半部分。
    //所以，我们假设如下定义，left指向最左侧，right指向最右侧，mid为二分之后的中间位置。
    //则，a[mid] >= a[left],说明mid位置在原数组前半部分，进一步说明，目标最小值，在mid的右侧，让left=mid
    //a[mid] < a[left], 说明mid位置在原数组后半部分，进一步说明，目标最小值，在mid的左侧，让right=mid
    //这个过程，会让[left, right]区间缩小
    //这个过程中，left永远在原数组前半部分，right永远在原数组的后半部分，而范围会一直缩小
    //当left和right相邻时，right指向的位置，就是最小元素的位置
    //但是，因为题目说的是非递减，也就意味着数据允许重复，因为有重复发，就可能会有a[left] == a[mid] ==a[right]的情况，
    // 我们就无法判定数据在mid左侧还是右侧。（注意，只要有两者不相等，我们就能判定应该如何缩小范围）


    //方法一


    public int minNumberInRotateArray1(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        } for(int i = 0; i < array.length-1; i++){
            if(array[i] > array[i+1]){
                return array[i+1];
            }
        } return array[0];
    }

    //方法二

    public int minNumberInRotateArray2(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        int mid = 0;
        while(array[left] >= array[right]){
            if(right - left == 1){
                mid = right;
                break;
            }
            mid = left + ((right - left)>>1);
            if(array[left] == array[right] && array[mid] == array[left]){ //1
                int result = array[left];
                for(int i = left+1; i < right; i++){ //left和right值是相等的
                    if(array[i] < result){
                        result = array[i];
                    }
                }
                return result;
            }
            if(array[mid] >= array[left]){
                //说明mid在原数组的前半部分
                // 如果array[mid] == array[left]， 上面1处的条件不满足且array[left] >=array[right]，则，array[mid] > array[right]
                left = mid;
            }
            else{
                right = mid;
            }
        }
        return array[mid];
    }


    /*10核心考点：数组操作，排序思想的扩展使用*/
    /*输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位
     于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。*/
    //解题思路：
    //这道题原题是不需要保证奇偶位置不变的。
    //现在新增了需求，解决方法也比较多，我们用较优方式解决一下，借鉴一下插入排序的思想

    public void reOrderArray(int [] array) {
        int k = 0;
        for(int i = 0; i < array.length; i++){
            if((array[i] & 1) == 1){//从左向右，每次遇到的，都是最前面的奇数，一定将来要被放在k下标处
                int temp = array[i];//现将当前奇数保存起来
                int j = i;
                while(j > k){//将该奇数之前的内容(偶数序列)，整体后移一个位置
                    array[j] = array[j-1];
                    j--;
                } array[k++] = temp;//将奇数保存在它将来改在的位置，因为我们是从左往右放的，没有跨越奇数，所以一定是相对位置不变的
            }
        }
    }

    /*数组中出现次数超过一半的数字
    * 1:使用hashmap来计算次数
    * 2:将数组排序,处于中心位置的数字必然是超过一半的数字
    * 3:将数组中俩个不同的数字消除,最后剩下的就是最多的数字*/

    public int MoreThanHalfNum_Solution1(int [] array) {
        //使用HashMap
        if(array == null){
            return 0;
        }
        HashMap<Integer,Integer> hashMap=new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            int k=array[i];
            if (!hashMap.containsKey(k)){
                hashMap.put(k,1);
            }else {
                hashMap.put(k,hashMap.get(k)+1);
            }
        }
        int half=array.length/2;
        for (int i = 0; i < array.length; i++) {
            if (hashMap.get(array[i]) > half){
                return array[i];
            }
        }
        return 0;
    }
    public int MoreThanHalfNum_Solution2(int [] array) {
        //使用数组排序的方法
        if(array == null){
            return 0;
        }
        Arrays.sort(array);
        int target = array[array.length/2];
        int count = 0;
        for(int i = 0; i < array.length; i++){
            if(target == array[i]){
                count++;
            }
        } if(count > array.length/2){
            return target;
        } return 0;
    }
    public int MoreThanHalfNum_Solution3(int [] array) {
        //使用消除俩个相同的数字的方法
        if(array == null){
            return 0;
        }
        int target=array[0];
        int times=1;
        for (int i = 1; i < array.length; i++) {
            if (times == 0){
                target=array[i];
                times=1;
            }
            if (array[i] == target){
                times++;
            }else {
                times--;
            }
        }
        times=0;
        for (int i = 0; i < array.length; i++) {
            if (target == array[i]){
                times++;
            }
        }
        return times > array.length/2 ? target : 0;
    }
    

}
